/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

#pragma once

#include <stack>
#include <cstdio>

template <typename Tv, typename Te> void Graph<Tv, Te>::bcc(int s) { 
   reset(); int clock = 0; int v = s; stack<int> S; 
   do
      if (UNDISCOVERED == status(v)) { 
         BCC(v, clock, S); 
         S.pop(); 
      }
   while (s != (v = (++v % n)));
}
#define hca(x) (fTime(x)) 
template <typename Tv, typename Te> 
void Graph<Tv, Te>::BCC(int v, int& clock, stack<int>& S) { 
   hca(v) = dTime(v) = ++clock; status(v) = DISCOVERED; S.push(v); 
   for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) 
      switch (status(u)) { 
         case UNDISCOVERED:
            parent(u) = v; status(v, u) = TREE; BCC(u, clock, S); 
            if (hca(u) < dTime(v)) 
               hca(v) = min(hca(v), hca(u)); 
            else { 
               /*DSA*/printf("BCC rooted at %c:", vertex(v));
               /*DSA*/stack<int> temp; 
			   do 
			   { 
				   temp.push(S.top()); print(vertex(temp.top()));
				   S.pop();
			   } 
			   while (v != temp.top()); 
			   while (!temp.empty()){
				   S.push(temp.top());
				   temp.pop();
			   }
               while (v != S.top())
				   S.pop(); 
               //S.push(v); //因为上一个while循环，所以这样处理结果
               /*DSA*/printf("\n");
            }
            break;
         case DISCOVERED:
            status(v, u) = BACKWARD;
            if (u != parent(v)) hca(v) = min(hca(v), dTime(u)); 
            break;
         default: 
            status(v, u) = (dTime(v) < dTime(u)) ? FORWARD : CROSS;
            break;
      }
   status(v) = VISITED; 
}
#undef hca
